package com.gxc.integer;

import java.util.HashSet;
import java.util.Set;

/**
 * 52. N 皇后 II
 * n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。
 *
 * 给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。
 */
public class TotalNQueens {

    public static void main(String[] args) {
/*        System.out.println(handle(4));
        System.out.println(handle(5));*/

        System.out.println(handle2(4));
        System.out.println(handle2(5));
    }

    /**
     * 递归
     * set记录每次选择的位置
     * @param n
     * @return
     */
    public static int handle(int n) {
        Set<Integer> cur = new HashSet<>();
        Set<Integer> left = new HashSet<>();
        Set<Integer> right = new HashSet<>();

        return recursion(cur, left, right, 0, n);
    }

    private static int recursion(Set<Integer> cur, Set<Integer> left, Set<Integer> right, int row, int n) {
        if (row == n) return 1;

        int leftIndex = 0;
        int rightIndex = 0;
        int sum = 0 ;
        for (int i = 0; i < n; i++) {
            //当前列已选
            if (cur.contains(i)) continue;

            //左斜线已选  从左上到右下方向，同一条斜线上的每个位置满足行下标与列下标之差相等，
            // 例如 (0,0) 和 (3,3) 在同一条方向一的斜线上。因此使用行下标与列下标之差即可明确表示每一条方向一的斜线。
            leftIndex = row - i;
            if (left.contains(leftIndex)) continue;
            //右斜线已选 右上到左下方向，同一条斜线上的每个位置满足行下标与列下标之和相等，
            // 例如 (3,0) 和 (1,2) 在同一条方向二的斜线上。因此使用行下标与列下标之和即可明确表示每一条方向二的斜线。
            rightIndex = row + i;
            if (right.contains(rightIndex)) continue;

            cur.add(i);
            left.add(leftIndex);
            right.add(rightIndex);
            sum = sum + recursion(cur, left, right, row+1, n);

            cur.remove(i);
            left.remove(leftIndex);
            right.remove(rightIndex);
        }
        return sum;
    }

    /**
     * 递归
     * 二进制位数计算每次皇后每次选择的位置
     * @param n
     * @return
     */
    public static int handle2(int n) {
        int cur = 0;
        int left = 0;
        int right = 0;
        return recursion2(cur, left, right, 0, n);
    }

    private static int recursion2(int cur, int left, int right, int row, int n) {
        if (row == n) return 1;

        //剩余可选的位置
        int selectable = ((1<<n) - 1) & (~(cur | left | right));
        int sum = 0;
        while (selectable != 0 ) {
            //选择低位的一个1
            int index = selectable & (-selectable);
            //低位的1 改为0
            selectable = selectable & (selectable - 1);
            sum += recursion2(cur | index, (left|index)>>1, (right|index)<<1, row+1, n);
        }
        return sum;
    }
}
